{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simple Implementation of Gradient Boosted Decision Tree For Regression\n",
    "\n",
    "#### for this implementation we use squared loss divided by 2 as loss function for GBDT\n",
    "\n",
    "$$L(y^{true}, y^{pred}) = \\frac{1}{2} (y^{true} - y^{pred})^2 $$\n",
    "\n",
    "so that our loss function gradient is \n",
    "$$y^{true} - y^{pred}$$ \n",
    "we will use this to compute residual"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### for the sake of example we use sklearn DecisionTreeRegressor as our tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.tree import DecisionTreeRegressor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GradientBoostedDecisionTreeRegressor:\n",
    "    def __init__(self, model_used, model_param={}, learning_rate=1e-4, n_trees=10):\n",
    "        \n",
    "        # the tree class that will be used\n",
    "        self.model_used = model_used\n",
    "        # the tree class parameter\n",
    "        self.model_param = model_param\n",
    "        \n",
    "        # learning rate for our GBDT\n",
    "        self.learning_rate = learning_rate\n",
    "        \n",
    "        # number of trees in our model\n",
    "        self.n_trees = n_trees\n",
    "        self.trees = []\n",
    "        self.initial_prediction = None\n",
    "        \n",
    "    def fit(self, X, y, verbose=False):\n",
    "        \n",
    "        # because we're using squared loss divided by 2 our initial prediction will be our label mean\n",
    "        self.initial_prediction = np.mean(y)\n",
    "        \n",
    "        last_y_pred = np.zeros(y.shape[0])+ self.initial_prediction\n",
    "        \n",
    "        # for every iteration we create new tree and update residual and predicted for training set\n",
    "        for i in range(self.n_trees):\n",
    "            \n",
    "            # the residual is the true value - our prediction, we want this to be 0\n",
    "            residual = y - last_y_pred\n",
    "            if verbose:\n",
    "                print('iteration num {}, mean residual {}'.format(i+1, np.mean(residual)))\n",
    "            # we train new tree on residual instead of y\n",
    "            dt = self.model_used(**self.model_param)\n",
    "            dt.fit(X, residual)\n",
    "            self.trees.append(dt)\n",
    "            \n",
    "            last_y_pred = last_y_pred + self.learning_rate * dt.predict(X)\n",
    "\n",
    "    def predict(self, X):\n",
    "\n",
    "        last_y_pred = np.zeros(X.shape[0])+ self.initial_prediction\n",
    "        \n",
    "        # for every tree update prediction by adding it to the last predicted value of last tree\n",
    "        for i in range(self.n_trees):\n",
    "            last_y_pred = last_y_pred + self.learning_rate * self.trees[i].predict(X)\n",
    "        return last_y_pred"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## usage example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train MSE: 3.1952\n",
      "Test MSE: 8.6603\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from sklearn import datasets\n",
    "from sklearn.utils import shuffle\n",
    "from sklearn.metrics import mean_squared_error\n",
    "\n",
    "\n",
    "boston = datasets.load_boston()\n",
    "X, y = shuffle(boston.data, boston.target, random_state=13)\n",
    "X = X.astype(np.float32)\n",
    "offset = int(X.shape[0] * 0.8)\n",
    "X_train, y_train = X[:offset], y[:offset]\n",
    "X_test, y_test = X[offset:], y[offset:]\n",
    "\n",
    "# #############################################################################\n",
    "# Fit regression model\n",
    "regressor = GradientBoostedDecisionTreeRegressor(DecisionTreeRegressor, {'max_depth':3}, n_trees=500, learning_rate=1e-2)\n",
    "\n",
    "regressor.fit(X_train, y_train, verbose=False)\n",
    "mse_train = mean_squared_error(y_train, regressor.predict(X_train))\n",
    "mse_test = mean_squared_error(y_test, regressor.predict(X_test))\n",
    "print(\"Train MSE: %.4f\" % mse_train)\n",
    "print(\"Test MSE: %.4f\" % mse_test)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
